P2569 [SCOI2010]股票交易

单调队列优化dp好题，难度约等于摆渡车

题解：

f[i][j]表示前i天，手上剩有j只股票最多能赚的钱

初始f[i][0]=0，其它都赋-inf

转移需要分类讨论：

1. 从0只股票开始买

直接计算花多少钱即可$f[i][j]=-AP_i*j$

2. 不进行任何买卖

直接从前一天的所有状态继承$f[i][j]=f[i-1][j]$

3. 从之前几天的基础上买入股票

首先要明确f[i][]是从f[i-w-1][]转移的

因为区间$[1,i-w-1)$内的状态，都可以通过情况2转移到f[i-w-1][]，所以只考虑这一天就够了

设第i-w-1天剩余k只股票，我们可以得到如下方程

$f[i][j]=\max \{ f[i-w-1][k]-(j-k) * AP_i | k \in [j-AS_i,j) \}$

复杂度是$O(nm^2)$的，所以考虑优化方程

展开

$f[i][j]=\max \{ f[i-w-1][k]-j AP_i+k AP_i | k \in [j-AS_i,j) \}$

提出

$f[i][j]=\max \{ f[i-w-1][k]+k AP_i | k \in [j-AS_i,j) \}-j AP_i$

此时发现唯一变量k的限制范围类似滑动窗口，且与k相关的值具有单调性，所有可以用单调队列维
护k

4. 从之前几天的基础上卖出股票

朴素方程如下：

$f[i][j]=\max \{ f[i-w-1][k]+(k-j) * BP_i | k \in (j,j+BS_i] \}$

化简后得到：

$f[i][j]=\max \{ f[i-w-1][k]+k BP_i | k \in (j,j+BS_i] \}-j BP_i$

与情况3同理可以用单调队列进行维护

特别的，情况3、4转移时为了让所有元素都能正常进出队列，要从较劣的一侧开始转移，即买入用顺序枚举，卖出用逆序枚举

显然的，f[i][j]的最终取值就是上述四种情况转移过来的最大值

最终答案就是f[n][0]，因为明显最后只有把股票都卖光才是最优的

代码

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=2e3+5;
int f[N][N],n,m,w,ap,bp,as,bs;

signed main(){
    read(n);read(m);read(w);
    memset(f,128,sizeof f);
    for(int i=1;i<=n;i++){
        read(ap);read(bp);read(as);read(bs);
        f[i][0]=0;
        for(int j=1;j<=as;j++) //从无股票的状态开始购买
            f[i][j]=-ap*j;
        for(int j=0;j<=m;j++) //不进行买卖，直接从上一天转移
            f[i][j]=max(f[i][j],f[i-1][j]);
        if(i<=w) continue; //防止负下标

        deque<int> buy;
        for(int j=0;j<=m;j++){ //从前面几天的基础上买入，正向转移
            while(!buy.empty()&&buy.front()<j-as) buy.pop_front(); //弹掉不在范围内的
            while(!buy.empty()&&f[i-w-1][buy.back()]+buy.back()*ap<=f[i-w-1][j]+j*ap) buy.pop_back(); //弹掉不优的
            buy.push_back(j); //加入新的
            f[i][j]=max(f[i][j],f[i-w-1][buy.front()]+buy.front()*ap-j*ap); //转移
        }

        deque<int> sell;
        for(int j=m;j>=0;j--){ //从前面几天的基础上卖出，反向转移
            while(!sell.empty()&&sell.front()>j+bs) sell.pop_front();
            while(!sell.empty()&&f[i-w-1][sell.back()]+sell.back()*bp<=f[i-w-1][j]+j*bp) sell.pop_back();
            sell.push_back(j);
            f[i][j]=max(f[i][j],f[i-w-1][sell.front()]+sell.front()*bp-j*bp);
        }
    }
    write(f[n][0]); //最优解最后肯定是全卖完的
}
赏

fighter